20240512 1553 - Hard - DP

1553. Minimum Number of Days to Eat N Oranges

simple dp will timeout because the n is too large to iterate

class Solution:
    def minDays(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[1] = 1
        for i in range(2, n+1):
            dp[i] = dp[i-1] + 1
            if i % 2 == 0:
                dp[i] = min(dp[i], dp[i//2]+1)
            if i % 3 == 0:
                dp[i] = min(dp[i], dp[i//3]+1)
        return dp[n]